# 对称二叉树: https://leetcode-cn.com/problems/symmetric-tree/submissions/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# 和100号算法题， 相同的树，可以说是一模一样
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        """
            这道题，归根到底，和第100道算法题， 相同的树，是一样的。 
            那道题是两个树是否相等， 这里是 一个树的左右子树是否相等（镜像对称），
            也本质就是 左子树按照 根左右的顺序遍历， 右子树按照根右左的顺序遍历，看节点是否相等

            那么使用深度优先遍历，解决这个问题
        """
        if not root: return True
        p = root.left
        q = root.right
        def traversal(node1, node2):
            # 1. 终止条件， 一个走到叶子节点了，或者这俩都走到叶子节点了
            if not node1 and not node2: return True
            if node1 is None or node2 is None: return False
            # 2. 当前“根”节点若不相等     
            if node1.val != node2.val: return False

            # 3. 当前左，右。 右，左节点进行比较。
            return traversal(node1.left, node2.right) and traversal(node1.right, node2.left)
        
        return traversal(p, q)


# 还可以进行 广度遍历解决
from collections import deque
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        """
            使用bfs，迭代的方式实现， 自顶向下
        """
        if not root: return True
        queue = deque()
        queue.append(root)
        queue.append(root)
        while queue:
            node1 = queue.popleft()
            node2 = queue.popleft()
            # 结构一样，都为None 就继续下一个节点判断
            if not node1 and not node2:
                continue
            # 否则这些情况，都是不对称
            if (node1 is None or node2 is None) or node1.val != node2.val:
                return False
            
            # 一个从左往右加， 一个从右往左加
            queue.append(node1.left)
            queue.append(node2.right)
            
            queue.append(node1.right)
            queue.append(node2.left)

        return True

